package com.azure.code.bfs;

import java.util.*;

/**
 * 773.Sliding Puzzle 滑动谜题
 * https://leetcode.cn/problems/sliding-puzzle/
 * 给你⼀个 2x3 的滑动拼图，⽤⼀个 2x3 的数组 board 表示。
 * 拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格⼦，
 * 你可以移动其中的数字，当 board 变为 [[1,2,3],[4,5,0]] 时，赢得游戏。
 *
 */
public class SlidingPuzzle_773 {

    public int slidingPuzzle(int[][] board) {
        int m = 2,n = 3;
        StringBuilder sb = new StringBuilder();
        String target = "123450";
        // 将2x3的数组转化成字符串数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(board[i][j]);
            }
        }
        /**
         *  0 1 2
         *  3 4 5
         *  记录一维字符串的相邻索引
         */
        String start = sb.toString();
        int[][] neighbor = {
                {1,3},
                {0,2,4},
                {1,5},
                {0,4},
                {3,1,5},
                {4,2}
        };

        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        Set<String> visited = new HashSet<>();
        int step = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0;i<sz;i++) {
                String cur = queue.poll();
                if(visited.contains(cur)){
                    continue;
                }
                if(cur.equals(target)){
                    return step;
                }
                visited.add(cur);
                // 找到数字0的index
                int idx = 0;

                for (;cur.charAt(idx)!='0';idx++);
                // 将数字0和相邻的数字交换位置
                for(int adj:neighbor[idx]) {
                    String new_board = swap(cur.toCharArray(),adj,idx);
                    queue.offer(new_board);
                }
            }
            step++;
        }
        return -1;
    }

    private String swap(char[] chs, int i, int j) {
        char temp = chs[i];
        chs[i] = chs[j];
        chs[j] = temp;
        return new String(chs);
    }

    public static void main(String[] args) {
        int[][] board = {{1,2,3},{4,0,5}};
        System.out.println(new SlidingPuzzle_773().slidingPuzzle(board));
    }
}
